package array;

/**
 * Created by fengliejv on 2017/11/22.
 */
public class FindPeakElement162 {
    //O(log(n)) solution
    public int findPeakElement(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        int left = 0;
        int rigit = nums.length - 1;
        int result = Integer.MIN_VALUE;
        while (left <= rigit) {
            int mid = (left + rigit) / 2;
            if (mid + 1 < nums.length && mid - 1 >= 0) {
                if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                    result = mid;
                    break;
                }
                if (nums[mid] < nums[mid + 1]) {
                    left = mid + 1;
                } else {
                    rigit = mid - 1;
                }
            }
            if (mid + 1 == nums.length) {
                if (nums[mid] > nums[mid - 1]) {
                    result = mid;
                    break;
                } else {
                    rigit = mid - 1;
                }
            }
            if (mid - 1 < 0) {
                if (nums[mid] > nums[mid + 1]) {
                    result = mid;
                    break;
                } else {
                    left = mid + 1;
                }
            }

        }
        return result;
    }

    //这个是O(n)的解法
    public int findPeakElement2(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        if (nums[0] > nums[1]) {
            return 0;
        }
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1] && nums[i] > nums[i - 1]) {
                return i;
            }
        }
        if (nums[nums.length - 1] > nums[nums.length - 2]) {
            return nums.length - 1;
        }
        return -1;
    }
}
